Section: New Results

Algèbre linéaire max-plus et convexité abstraite/Max-plus linear algebra and abstract convex analysis

Convexité max-plus ou tropicale/Max-plus or tropical convexity

Participants : Xavier Allamigeon, Stéphane Gaubert, Eric Goubault [CEA] , Ricardo Katz [Conicet, Argentine] .

On étudie les analogues max-plus ou tropicaux des ensembles convexes. Ceux-ci sont utiles en particulier pour représenter de manière effective les ensembles d'états accessibles de systèmes à événements discrets [9] , ils sont aussi apparus récemment en géométrie tropicale, dans toute une série de travaux à la suite de Sturmfels et Develin  [114] . Les polyèdres max-plus peuvent aussi être vus comme des limites de déformations de polyèdres classiques, sur lesquels ils donnent un éclairage de nature combinatoire. Toutes ces motivations ont inspiré la recherche d'analogues des résultats fondamentaux d'analyse convexe classique: séparation, projection, points extrémaux, à la suite en particulier de [8] .

Dans un travail de X. Allamigeon, S. Gaubert, et E. Goubault  [83] , [57] , on a mis en évidence un critère combinatoire pour la caractérisation des sommets des polyèdres tropicalement convexes. Celui-ci s'exprime à l'aide d'hypergraphes orientés, et de leurs composantes fortement connexes. Ce critère possède la propriété d'être vérifiable en un temps presque linéaire en la taille de l'hypergraphe.

On en déduit un analogue tropical de la méthode de la double description [57] (méthode très utilisée sur les polyèdres classiques, et dûe à Motzkin et al.  [158] ). Cet algorithme permet de calculer les sommets d'un polyèdre défini de façon externe (intersection de demi-espaces ou d'hyperplans tropicaux). Grâce au critère combinatoire précédent, l'algorithme améliore de plusieurs ordres de grandeur les techniques connues jusqu'alors. Ceci est confirmé par de nombreuses expérimentations. Ce travail est motivé par des applications à l'analyse statique  [82] et aux systèmes à événements discrets  [116] , dans lesquelles la manipulation de tels polyèdres est le goulot d'étranglement.

Dans un travail de X. Allamigeon, S. Gaubert, et R. Katz [57] , on étend le théorème de McMullen au cas tropical: ce dernier caractérise le nombre maximal de points extrêmes d'un polyèdre, en fonction du nombre d'inégalités qui le définissent et de sa dimension. Nous montrons que la même borne est valide dans le cas tropical (à une modification triviale près). Cependant, le calcul de la borne optimale est encore ouvert dans ce cas.

Dans un travail de S. Gaubert et R. Katz [26] , on étudie la représentation d'un polyèdre tropical comme intersection de demi-espaces, ou si l'on préfère, comme conjonction d'inégalités affines. Nous donnons notamment un contre-exemple, montrant les inconvénients de la représentation en termes de demi-espaces minimaux proposée précédemment dans la littérature tropicale.

Il est connu qu'un polyèdre tropical peut être représenté comme l'enveloppe convexe d'un ensemble minimal de points et rayons, donnés par ses sommets et ses rayons extrêmes  [125] . Dans un travail débuté par X. Allamigeon et R. Katz, et effectué en partie lors d'une visite de R. Katz à l'INRIA (juillet 2001), on étudie la question duale de la caractérisation des représentations minimales par demi-espaces. On montre qu'un polyèdre tropical possède essentiellement une unique représentation minimale par demi-espaces, lorsque leur apex appartiennent au polyèdre. On montre que les apex de ces demi-espaces non-redondants correspondent à certains sommets du complexe tropical introduit par Develin et Sturmfels  [114] . On introduit également un critère combinatoire pour l'élimination de demi-espaces redondants à l'aide d'hypergraphes orientés.

English version

We study the max-plus or tropical analogues of convex sets. These have been used in particular to represent effectively the accessible sets of certain discrete event systems [9] . They also appeared in tropical geometry, following the work of Sturmfels and Develin  [114] . Max-plus polyhedra can be thought of as limits of deformations of classical polyhedra, on which they give a combinatorial insight. These motivations have inspired the investigation of analogues of basic results of classical convex analysis: separation, projection, representation by extreme points, following [8] .

In a work of X. Allamigeon, S. Gaubert, and E. Goubault [57] , we introduce a combinatorial criterion for the characterization of the vertices of tropically convex polyhedra. It is expressed in terms of directed hypergraphs and their strongly connected components. This criterion can be verified in almost linear time in the size of the hypergraph.

This allows to develop a tropical analogue of the double description method [57] (this method is widely used for classical convex polyhedra, and is due to Motzkin et al.  [158] ). This algorithm is able to determine all the vertices of a polyhedron defined externally (intersection of tropical half-spaces of hyperplanes). Thanks to the combinatorial criterion mentioned above, the algorithm improves the existing methods by several orders of magnitude. This is confirmed by several experiments. This is motivated by applications to static analysis  [82] and discrete event systems  [116] , in which computing such polyhedra turns out to be the bottleneck.

In a work of X. Allamigeon, S. Gaubert, and R. Katz [19] , we extend the McMullen upper bound theorem to the tropical case. This theorem characterises the maximal number of extreme points of a polyhedron, as a function of the number of inequalities defining it, and of the dimension. We show that the same bound is valid in the tropical case (up to a trivial modification). However, computing the optimal bound is an open problem in this case.

In a work of S. Gaubert and R. Katz [26] , we study the representation of a tropical polyhedron as an intersection of half-spaces. We give in particular a counter example, showing some inconvenients of the representation in terms of minimal half-spaces proposed previously in the tropical litterature.

It is well-known that a tropical polyhedron can be represented as the convex hull of a minimal set of points and rays, provided by its vertices and extreme rays  [125] . In an ongoing work of X. Allamigeon and R. Katz, partly done during the visit of R. Katz at INRIA (July 2011), the dual problem of characterizing the minimal representations by half-spaces is studied. We show that a tropical polyhedron admits essentially a unique minimal external representation by half-spaces, provided that their apices belong to the polyhedron. We prove that the apices of these half-spaces correspond to certain vertices of the tropical complex introduced by Develin and Sturmfels  [114] . We also establish a combinatorial criterion allowing to eliminate redundant half-spaces using directed hypergraphs.

Convexes max-plus et jeux avec paiements ergodiques/Max-plus convex sets and mean payoff games

Participants : Marianne Akian, Xavier Allamigeon, Stéphane Gaubert, Alexander Guterman [Moscow State University] , Ricardo Katz [Conicet, Argentine] , Sergei Sergeev.

Dans un travail d'Akian, Gaubert et Guterman [16] , on montre un résultat d'équivalence entre les jeux ergodiques à somme nulle et les systèmes d'inégalités max-plus linéaires: décider la non-vacuité d'un polyèdre tropical est équivalent à vérifier si un jeu déterministe à somme nulle a un paiement moyen par unité de temps positif ou nul. Plus généralement, la même question pour un jeu stochastique à somme nulle est équivalente à vérifier si un convexe tropical (non-polyédral, i.e., défini par un système infini d'inégalités) est vide. Ces résultats sont démontrés à l'aide de techniques de théorie de Perron-Frobenius non-linéaire. Ils sont ensuite appliqués à l'étude de l'indépendance linéaire dans le semi-anneau tropical.

Le résultat de [16] a eu plusieurs retombées.

D'une part, dans un travail d'Allamigeon, Gaubert, et Katz [20] , on établit un analogue tropical du théorème de Farkas: on montre que décider si une inégalité max-plus linéaire est une conséquence logique d'une famille de telles inégalités est également équivalent à un problème de jeu ergodique. Le travail [20] comprend aussi une description des “faces” (ou plus précisément, des points extrêmes du polaire) d'un polyèdre tropical en termes de transversaux minimaux dans un hypergraphe.

D'autre part, dans un travail de Gaubert et Sergeev  [127] , on réduit le problème spectral tropical de type faisceaux, $Ax=\lambda Bx$, à un jeu paramétrique (ce qui permet de calculer le spectre en temps pseudo-polynômial).

Enfin, dans un travail de Gaubert, Katz, et Sergeev [27] , on développe un algorithme de programmation linéaire tropicale (pseudo-polynômial) basé sur cette correspondance avec les jeux répétés. Allamigeon et Sergeev ont développé récemment un logiciel prototype en ocaml afin d'expérimenter cet algorithme. Ce logiciel inclus en particulier, en guise d'oracles résolvant des problèmes de jeux répétés, l'algorithme d'itération sur les politiques de Gaubert-Gunawardena  [124] dans sa version de  [115] , la modification de cet algorithme due à Chaloupka  [98] , ainsi que l'algorithme d'itérations sur les politiques de Björklund-Vorobyov  [91] .

English version

In [16] , we show the equivalence mean payoff games and max-plus linear inequalities: testing whether a tropical polyhedron is non-empty is equivalent to checking whether a mean payoff deterministic game is winning. More generally, checking whether a mean payoff stochastic game is winning is equivalent to checking the non-emptyness of a tropical convex set defined by an infinite family of inequalities. These results are established using techniques of non-linear Perron-Frobenius theory. Then, they are applied to the study of linear independence over the tropical semiring.

The equivalence established in [16] had several consequences.

First, a work of Allamigeon, Gaubert, and Katz [20] yields a tropical analogue of Farkas theorem: we show that deciding whether a max-plus linear inequality follows from a family of such inequalities is also equivalent to solving a mean payoff game. Moreover, the work [20] comprises a characterization of the “faces” (more precisely, the extreme points of the polar) of a tropical polyhedra in terms of minimal transversals of a hypergraph.

Next, in a work of Gaubert and Sergeev  [127] , the tropical spectral problem for matrix pencils, $Ax=\lambda Bx$, is reduced to a parametric game (which allows one to compute the spectrum in pseudo-polynomial time).

Finally, in a work of Gaubert, Katz, and Sergeev [27] , a (pseudo-polynomial) tropical linear programming algorithm is developed, based on the same correspondence with mean payoff games. Allamigeon and Sergeev developed recently an ocaml prototype in order to experiment this method. This prototype includes in particular mean payoff game solvers, namely the version of  [115] of the policy iteration algorithm of Gaubert-Gunawardena  [124] , the modification of this algorithm by Chaloupka  [98] , as well as the policy iteration algorithm of Björklund-Vorobyov  [91] .

Meilleure approximation par des semi-modules max-plus pour la métrique projective de Hilbert/Best approximation in Hilbert's projective metric by max-plus semimodules

Participants : Marianne Akian, Stéphane Gaubert, Viorel Nitica [West Chester University (US) and IMAR (Bucharest, Romania)] , Ivan Singer [IMAR (Bucharest, Romania)] .

Nous étudions les projecteurs sur des espaces linéaires max-plus, ainsi que les demi-espaces max-plus séparants. Dans [18] , nous obtenons de nouvelles propriétés concernant ces objets, ce qui nous permet de déduire une formule explicite de la distance d'un point à un demi-espace max-plus pour la métrique projective de Hilbert, ainsi qu'une caractérisation de l'ensemble des points minimisants de cette distance. Nous obtenons aussi un algorithme de type projection cyclique permettant de résoudre des systèmes d'inégalités linéaires max-plus. Ce travail est effectué dans le cadre d'un projet LEA Math mode.

English version

We are studying projectors on max-plus linear spaces, as well as separating half-spaces over the max-plus semiring. In [18] , we establish new results, and derive an explicit formula for the distance in Hilbert's projective metric between a point and a half-space, as well as explicit descriptions of the set of minimizers of this distance. We also obtain, as a consequence of the previous results, a cyclic projection type algorithm to solve systems of max-plus linear inequalities. This work is carried out as part of a LEA Math-mode project.

Miscellanées en algèbre linéaire max-plus/Topics in max-plus linear algebra

Participant : Sergei Sergeev.

Pendant son année de séjour post-doctoral dans l'équipe, S. Sergeev a collaboré avec celle-ci sur les questions de convexité tropicale et de jeux répétés (voir §  6.2.2 supra). Il a en outre mené des recherches touchant à diverses questions d'algèbre linéaire max-plus, en collaboration avec plusieurs coauteurs étrangers [37] , [66] , [63] , [67] .

English version

During his one year post-doctoral stay, S. Sergeev collaborated with team members on tropical convexity and mean payoff game problems (§  6.2.2 supra). In addition, the following research has been developed with several international coauthors.

• Z-matrix equations and weakly stable matrices. Sergeev continued his joint research with P. Butkovič and H. Schneider on traditional topics of max-plus linear algebra. They described solution set to Z-matrix equations $\lambda x=Ax\oplus b$, comparing the results with nonnegative matrix setting (old works of H. Schneider with coauthors) and extending them to linear algebra over more general semirings. Weakly stable matrices are such that the set of vectors $x$ whose orbit $A^{k}x$ converges to an eigenvector, is exactly the eigenvector cone. The weak stability was characterized in terms of relations between spectral classes of $A$ and the critical graph in each strongly connected component.

• CSR expansions. Sergeev continued his research on CSR expansions of matrix powers in max-plus algebra, see the accepted paper with H. Schneider [37] , and paper with T. Nowak in preparation, which is going to be a survey on transience bounds in max-plus algebra based on CSR expansion schemes. New results may be applied in analysing the performance of reversal routing and reversal scheduling algorithms in collaboration with the team of B. Charron-Bost (École Polytechnique).

• Ultradiscrete KdV. Sergeev learned about the ultradiscrete KdV model at the conferences in Manchester (April 2011) and Glasgow (July 2011), and worked on the application of max-plus spectral theory to the ultradiscrete analogue of the Lax pair studied recently by R. Willox, J. Satsuma, J. Nimmo and others, based on the idea of S. Gaubert (who also took part in both conferences). In submission [66] , he suggested the notion of pairs of fundamental eigenvectors associated with each soliton and showed that the problem can be reduced to finite-dimensional spectral theory with two additional constraints. In some special cases the problem can be solved by means of fundamental eigenvectors, which can be also used in the operation of undressing. However, in the case of several massive solitons the fundamental eigenvectors can never provide a solution, and more elaborate theory is needed.

• max-Łukasiewicz algebra Sergeev learned about some new fuzzy linear algebras during his research visit to Czech Republic. He observed that the linear algebraic problems over max-Łukasiewicz algebra, defined in the interval $[0,1]$ with operations $a\otimes b:=max(a+b-1,0)$ and $a\oplus b:=max(a,b)$ can be reduced to some problems over max-plus algebra. This observation, being used in submission [63] has led to a new collaboration with Martin Gavalec and his group at the University of Hradec Kralove.

• Visualization scaling and multi-objective optimization. Sergeev continued his research on diagonal similarity scalings in max-plus algebra, see submission [67] and new collaboration with B. Benek Gursoy and O. Mason (in preparation). In this new collaboration, the authors analyze the possibilities of simultaneous matrix scaling (visualization), the special case of symmetrically reciprocal matrices, and extension to Pareto optimality.